// 相交链表
/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */

/**
 * @param {ListNode} headA
 * @param {ListNode} headB
 * @return {ListNode}
 */
 var getIntersectionNode = function(headA, headB) {
    /*let l = headA.next ;
    let r = headB.next ;
    if(r||l) return null;
    while(r) {
     if(r==l) {
         return r
     }
     while(l) {
         l = l.next;
         if(r==l) {
         return r
     }
     r=r.next;
     l=headA.next;
     }
    }
    return null;*/
    /*if (headA === null || headB === null) {
        return null;
    }
    let pA = headA, pB = headB;
    while (pA != pB) {
        pA = pA === null ? headB : pA.next;
        pB = pB === null ? headA: pB.next;
    }
    return pA;
    */
    /*let res = new Set();
    let pa=headA;
    let pb=headB;
   while(pa!=null){
       res.add(pa);
       pa=pa.next;
   }
   while(pb!=null) {
       if(res.has(pb)) {
           return pb;
       }
       pb=pb.next;
   }
   return null;
   */
    let lastHeadA = null;
    let lastHeadB = null;
    let originHeadA = headA;
    let originHeadB = headB;
    if (!headA || !headB) {
        return null;
    }
    while (true) {
        if (headB == headA) {
            return headB;
        }
        if (headA && headA.next == null) {
            lastHeadA = headA;
            headA = originHeadB;
        } else {
            headA = headA.next;
        }
        if (headB && headB.next == null) {
            lastHeadB = headB
            headB = originHeadA;
        } else {
            headB = headB.next;
        }
        if (lastHeadA && lastHeadB && lastHeadA != lastHeadB) {
            return null;
        }
    }
    return null;
};